package com.goudan.practice.linkedlist;

/**
 * 绘画展览门票每张5元，如果有2n个人排队购票，每人一张，并且其中一半人恰只有5元钱，另一半人恰只有10元钱，而票房无零钱 可找，
 * 那么如何将这2n个人重新排成一列，顺次购票，使得不至于因票房无零钱可找而耽误时间，应该采用什么算法解决呢？要求最小代价。
 */
public class BuyTicket {

    public static class Node {
        public int value;
        public Node next;
        public String name;

        public Node(int v) {
            value = v;
        }
    }

    public static void main(String[] args) {
//        int[] req = {10, 5, 10, 10, 10, 5, 5, 5};
//        int[] req = {10, 10, 5, 5};
//        int[] req = {5, 10, 10, 10, 5, 5};
        int[] req = {5, 10, 10, 5, 10, 5};
        Node head = ArrToLinked(req);
        printLinkedList(head);
        // 重新调整队伍
        Node newHead = reLineUp(head);
        printLinkedList(newHead);
    }

    /**
     * 重新调整队伍
     */
    private static Node reLineUp(Node head) {
        if (head == null || head.next == null) return head;
        // 如果队头就是10元客户，去后面找到最近的5元客户插入到队头
        if (head.value == 10) {
            head = findNearFive(null, head);
            printLinkedList(head);
        }
        // 第一个必然是5元客户，从第二个客户往后开始重新排序
        Node start = head.next;
        Node pre = head;
        // 代表还剩余多少张5块钱，默认0
        int flag = 1;
        while (start != null) {
            if (start.value == 5) {
                flag++;
                start = start.next;
                pre = pre.next;
            } else {
                // 如果没有5块钱可以找零，去队伍后面找最近的5元钱客户插入到当前客户前面,让后继续检查下一位客户
                if (flag == 0) {
                    findNearFive(pre, start);
                    pre = pre.next.next;
                } else {
                    flag--;
                    pre = pre.next;
                }
                start = start.next;
            }
        }
        return head;
    }

    /**
     * 从当前位置后一个节点找到第一个五放到指定节点前面
     */
    private static Node findNearFive(Node pre, Node start) {
        Node temp = start.next;
        Node startPre = start;
        while (temp != null) {
            if (temp.value == 5) {
                if (pre == null) {
                    pre = temp;
                } else {
                    pre.next = temp;
                }
                System.out.println(temp.name + "插入到" + start.name + "的前面");
                startPre.next = temp.next;
                temp.next = start;
                return pre;
            } else {
                temp = temp.next;
                startPre = startPre.next;
            }
        }
        return pre;
    }

    /**
     * 辅助方法：打印链表
     */
    private static void printLinkedList(Node head) {
        if (head == null) System.out.println("链表为空");
        Node tem = head;
        while (tem != null) {
            System.out.print(tem.value + "-->");
            tem = tem.next;
        }
        System.out.println("end");
    }

    /**
     * 辅助方法：数组转链表
     */
    private static Node ArrToLinked(int[] req) {
        if (req == null || req.length == 0) {
            return null;
        }
        Node head = new Node(req[0]);
        Node tem = head;
        head.name = "第1位客户";
        for (int i = 1; i < req.length; i++) {
            tem.next = new Node(req[i]);
            tem.next.name = "第" + (i + 1) + "位客户";
            tem = tem.next;
        }
        return head;
    }

}
